package com.future;

/**
 * Description:  ����������
 * ����һ���������� nums �������ҳ�һ���������͵����������飨���������ٰ���һ��Ԫ�أ������������͡�
 * <p>
 * ������ �������е�һ���������֡�
 * <p>
 * ʾ�� 1��
 * <p>
 * ���룺nums = [-2,1,-3,4,-1,2,1,-5,4]
 * �����6
 * ���ͣ�����������?[4,-1,2,1] �ĺ����Ϊ?6 ��
 * <p>
 * ��Դ�����ۣ�LeetCode��
 * ���ӣ�https://leetcode-cn.com/problems/maximum-subarray
 * ����Ȩ������������С���ҵת������ϵ�ٷ���Ȩ������ҵת����ע��������
 *
 * @Author: future
 * @Date:2022/3/22:23:48
 */
public class Solution_53 {
    public static void main(String[] args) {
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        nums = new int[]{5, 4, -1, 7, 8};
        nums = new int[]{1, -2, 9, -8, 10, 12, -20, -1, -9, 20, -5, 10};
        System.out.println(maxSubArray(nums));
        System.out.println(maxSubArray_dp(nums));
    }

    /**
     * �Ż���
     * ˼·��
     * �������ҹ���������ǰ����ĺ�
     * nums={1, -2, 9, 10, 12, -20, -9, 20,}
     * 1��i=0 val = nums[0]=1;
     * 2��i=1 val = -1(-2��һ�������������Լ�);
     * 3��i=2 val = 9(ǰ����-1,С��0�����ֻ����٣������Լ��������ֵ);
     * ע�⣺Ϊ�˼��٣�ÿһ��ѭ������ʵʱ����ans��
     * ......
     * ѭ�����ַ�����β
     * ����ans
     *
     * @param nums
     * @return
     */
    public static int maxSubArray_dp(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int N = nums.length;
        int[] dp = new int[N];
        dp[0] = nums[0];
        int ans = dp[0];
        for (int i = 1; i < N; i++) {
            int val = Math.max(nums[i], nums[i] + dp[i - 1]);
            dp[i] = val;
            ans = Math.max(val, ans);
        }
        return ans;
    }

    private static int process_dp(int index, int[] nums, int sum) {
        if (index < 0) {
            return sum;
        }
        int v = process_dp(index - 1, nums, sum + nums[index]);
        return Math.max(v, sum);
    }

    /**
     * ��������
     *
     * @param nums
     * @return
     */
    public static int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int ans = Integer.MIN_VALUE;
        int N = nums.length;
        for (int i = 0; i < N; i++) {
            ans = Math.max(ans, process(i - 1, nums, nums[i]));
        }
        return ans;
    }

    private static int process(int index, int[] nums, int sum) {
        if (index < 0) {
            return sum;
        }
        int v = process(index - 1, nums, sum + nums[index]);
        return Math.max(v, sum);
    }
}
